package com.sxu.greedy.day5;

import java.util.HashMap;
import java.util.Map;

/**
 * 397 整数替换
 *  递归 + 记忆化搜索
 */
public class Test24_2 {

    // 添加备忘录
    Map<Long, Integer> hash;

    public int integerReplacement(int n) {
        hash = new HashMap<Long, Integer>();
        return dfs(n * 1L);
    }

    // 将dfs改为记忆化搜索
    public int dfs(long n) {
        if(hash.containsKey(n)){
            return hash.get(n);
        }
        if(n == 1){
            hash.put(n, 0);
            return hash.get(n);
        }
        if(n%2 == 0){
            hash.put(n, 1 + dfs(n/2));
            return hash.get(n);
        } else {
            hash.put(n, 1 + Math.min(dfs(n-1),dfs(n+1)));
            return hash.get(n);
        }
    }
}
